10819 차이를 최대로 {boj} {permutation}

• https://www.acmicpc.net/problem/10819
• next_permutation 구현
• next_combination 구현하기

C++ 코드

#include<iostream>
#include<vector>
#include<climits>
#include<cmath>
#include<algorithm>
using namespace std;

int max_diff(vector<int>& seq);
int sum_diff(const vector<int>& seq);
bool next_permu(vector<int>& seq);
bool prev_permu(vector<int>& seq);
void swap(int& a, int& b);

int main(void)
{
	int n = 0;
	cin >> n;
	vector<int> seq(n);
	for (int i = 0; i < n; i++) cin >> seq[i];
	sort(seq.begin(), seq.end());
	cout << max_diff(seq) << '\n';
	return 0;
}
int sum_diff(const vector<int>& seq)
{
	int ret = 0;
	for (int i = 0; i < seq.size()-1; i++)
		ret += abs(seq[i] - seq[i+1]);
	return ret;
}
int max_diff(vector<int>& seq)
{
	int ret = INT_MIN;
	ret = max(ret, sum_diff(seq));
	// <algorithm> header 의 next_permutation() 함수는 시간초과가 발생하지 않는다.
	//while(next_permutation(seq.begin(), seq.end())) ret = max(ret, sum_diff(seq));		
	while(next_permu(seq)) {			// 왜 시간초과가 발생하지?
		ret = max(ret, sum_diff(seq));
#if DBG > 0
for (auto i : seq) cout << i << ' ';
cout << '\n';
#endif
	}
	//while(prev_permu(seq)) ret = max(ret, sum_diff(seq));
	return ret;
}
bool next_permu(vector<int>& seq)
{
	int i = 0, j = 0;
	for (i = seq.size()-1; i >= 0; i--){
		if (i == 0) return false;
		if (seq[i-1] < seq[i]) break;
	}
	for (j = i; j < seq.size()-1; j++)
		if (seq[j+1] <= seq[i-1]) break;
	swap(seq[i-1], seq[j]);
	
	for (int k = seq.size()-1; k > i; k--)
		swap(seq[i++], seq[k]);
	return true;
}
bool prev_permu(vector<int>& seq)
{
	int i = 0, j = 0;
	for (i = seq.size()-1; i >= 0; i--){
		if (i == 0) return false;
		if (seq[i-1] > seq[i]) break;
	}
	for (j = i+1; j < seq.size(); j++)
		if (seq[j+1] > seq[i-1]) break;
	swap(seq[i-1], seq[j-1]);
	
	for (int k = seq.size()-1; k > i; k--)
		swap(seq[i++], seq[k]);
	return true;
}
void swap(int& a, int& b)
{
	int tmp = a;
	a = b;
	b = tmp;
}